package j2025.j01;

import java.util.PriorityQueue;

/**
 * @Author 猫大仙
 */
public class j0128 {

}

/**
 * 295. 数据流的中位数
 * 中位数是有序整数列表中的中间值。如果列表的大小是偶数，
 * 则没有中间值，中位数是两个中间值的平均值。
 *
 * 例如 arr = [2,3,4] 的中位数是 3 。
 * 例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。
 * 实现 MedianFinder 类:
 *
 * MedianFinder() 初始化 MedianFinder 对象。
 *
 * void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
 *
 * double findMedian() 返回到目前为止所有元素的中位数。
 * 与实际答案相差 10-5 以内的答案将被接受。
 */
class MedianFinder{
    PriorityQueue<Integer> Lheap;
    PriorityQueue<Integer> Rheap;
    public MedianFinder() {
        Lheap = new PriorityQueue<>((a,b)->b-a);//左半大根堆
        Rheap = new PriorityQueue<>();//右半小根堆
    }

    public void addNum(int num) {
        if(Lheap.size()==Rheap.size()){
            if(Lheap.isEmpty() || num<=Lheap.peek()){
                Lheap.offer(num);
            }else{
                Rheap.offer(num);
                int tmp = Rheap.poll();
                Lheap.offer(tmp);
            }
        }else if (Lheap.size()>Rheap.size()){
            if(num<=Lheap.peek()){
                Lheap.offer(num);
                int tmp = Lheap.poll();
                Rheap.offer(tmp);
            }else{
                Rheap.offer(num);
            }
        }
    }

    public double findMedian() {
        if(Lheap.size()>Rheap.size()){
            return Lheap.peek();
        }else {
            return (Lheap.peek()+Rheap.peek())/2.0;
        }
    }
}
